package lcof;

import pojo.TreeNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;

/**
 * @author 江岸
 * @version V1.0
 * @ClassName: KthLargest54
 * @description: 剑指 Offer 54. 二叉搜索树的第k大节点
 * 给定一棵二叉搜索树，请找出其中第k大的节点。
 * @date 2021/5/617:34
 * @since V1.0
 */
public class KthLargest54 {
    public int kthLargest(TreeNode root, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        Deque<TreeNode> dq = new LinkedList<>();
        TreeNode t = root;
        while (t!=null || !dq.isEmpty()){
            if (t!=null){
                dq.push(t);
                t  =t.left;
            }else {
                TreeNode pop = dq.pop();
                list.add(pop.val);
                t = pop.right;
            }
        }
        return list.get(list.size()-k);
    }


    /**
     * 根据以上性质，易得二叉搜索树的 中序遍历倒序 为 递减序列 。
     * 因此，求 “二叉搜索树第 kk 大的节点” 可转化为求 “此树的中序遍历倒序的第 kk 个节点”。
     *
     */
    int res, k;
    public int kthLargest2(TreeNode root, int k) {
        this.k = k;
        dfs(root);
        return res;
    }
    void dfs(TreeNode root) {
        if(root == null) return;
        dfs(root.right);
        if(k == 0) return;
        if(--k == 0) res = root.val;
        dfs(root.left);
    }


}
